/*-------------------------------------------------------------------------
 *
 * trgm_regexp.c
 *	  使用三元组进行正则表达式匹配。
 *
 * 三元组索引支持正则表达式（regex）搜索的一般思路是将正则表达式转换为三元组上的逻辑表达式。
 * 例如：
 *
 *	 (ab|cd)efg  =>  ((abe & bef) | (cde & def)) & efg
 *
 * 如果一个字符串匹配正则表达式，则它必须匹配三元组上的逻辑表达式。然而，反之不一定成立：一个匹配逻辑表达式的字符串可能不匹配原始的正则表达式。这种误报通过重新检查来消除，具体方法是在检索到的堆元组上运行常规的正则表达式匹配操作符。
 *
 * 由于三元组表达式涉及 AND 和 OR 运算符，我们不能期望核心索引机制完全评估它。相反，正则表达式分析的结果是一组需在索引中查找的三元组，以及一个简化的图，用于通过 trigramsMatchGraph() 确定特定索引值是否匹配该表达式。
 *
 * 将正则表达式转换为三元组表达式是基于对与正则表达式对应的自动机的分析。该算法包含四个阶段：
 *
 * 1) 将正则表达式编译为 NFA 形式。这由 PostgreSQL 的正则表达式库处理，该库提供了对其不透明的 regex_t 结构的访问，以暴露 NFA 状态图和作为状态转换标签的“颜色”（等价字符集）。
 *
 * 2) 将原始 NFA 转换为扩展图，其中弧的标签是必须存在的三元组，以便通过弧从一个状态移动到另一个状态。该阶段使用的三元组由颜色组成，而不是原始 NFA 中的字符。
 *
 * 3) 将颜色三元组扩展为由字符组成的常规三元组。如果产生的不同三元组太多，则会消除三元组，简化图，直到它简单到足够的程度。
 *
 * 4) 最后，将结果图打包到一个 TrgmPackedGraph 结构中，并返回给调用者。
 *
 * 1) 将正则表达式编译为 NFA 形式
 * ---------------------------------
 * 正则表达式编译器返回的自动机是一个图，其中顶点是“状态”，弧是用颜色标记的。每种颜色代表一个字符集，因此所有分配给同一颜色的字符在匹配正则表达式时都是可以互换的。存在两个特殊状态：“初始”和“最终”。一个状态可以有多个用相同颜色标记的外发弧，这使得自动机是非确定性的，因为它可以同时处于多个状态。
 *
 * 请注意，这个 NFA 与原始正则表达式相比已经是有损的，因为它忽略了一些正则表达式特性，如前瞻约束和回溯匹配。对于我们的目的来说，这没关系，因为只有匹配 NFA 的字符串才有可能满足正则表达式。
 *
 * 2) 将原始 NFA 转换为扩展图
 * ----------------------------------------------------
 * 在第二阶段，自动机转换为基于原始 NFA 的图。扩展图中的每个状态表示原始 NFA 中的一个状态，以及一个标识进入该状态前看到的最后两个字符（更准确地说是颜色）的前缀。根据可以在其之前的字符，可以在扩展图中为原始 NFA 中的每个状态有多个状态。如果前缀位置“不明确”，则前缀位置可以是“未知”，如果字符是非单词字符，则可以是“空白”（我们不需要区分它们是哪个非单词字符，因此只需将它们视为空白）。
 *
 * 为便于描述，将扩展状态标识符（两个前缀颜色加上原始 NFA 的状态编号）称为“进入键”。
 *
 * 扩展图的每个弧都用一个三元组标记，该三元组必须在字符串中存在才能匹配。我们可以通过将扩展状态的前缀与基础出弧的颜色标签组合，构建这个出弧，前提是两个前缀位置都不是“未知”。但是请注意，三元组中的一些颜色可能是“空白”的。这是可以的，因为我们想生成字边界三元组，就像常规三元组机制那样，如果我们知道某些单词字符必须在所有匹配 NFA 的字符串中与字边界相邻。
 *
 * 扩展图的状态数也可能少于原始 NFA，因为除非状态是通过有效弧可达，我们不麻烦单独创建状态条目。当从扩展图的一个状态可以到达一个进入键，但我们不知道与该转换相关的完整三元组时，我们无法创建有效弧；相反，我们将进入键插入源状态的 enterKeys 列表。这有效地意味着基于检查三元组，两个扩展状态不能可靠地区分。
 *
 * 因此，扩展图类似于原始 NFA，但弧用三元组标记，而不是单个字符，并且可能有更多或更少的状态。这是原始 NFA 的一种有损表示：匹配原始正则表达式的任何字符串必须匹配扩展图，但反向不成立。
 *
 * 我们通过对从初始状态可达的状态进行宽度优先遍历来构建扩展图。在每个可达状态，我们识别出可以从此状态可到达的状态，而不遍历可预测的三元组，并将这些状态的进入键添加到当前状态。然后我们生成所有外部弧，指向这个状态集合中的目标状态，这些外发弧具有可预测的三元组，并将它们的目标状态添加到待检查的状态队列中。
 *
 * 在构建图时，如果状态或弧的数量超过预定义的限制，我们就放弃，并简单地将任何尚未处理的状态标记为最终状态。大致而言，这意味着我们利用了正则表达式的开头的一部分。此外，任何成员字符过多的颜色都会被视为“未知”，因此我们不能从中推导三元组。
 *
 * 3) 将颜色三元组扩展为常规三元组
 * --------------------------------------------------
 * 扩展图中的三元组是“颜色三元组”，由必须出现在字符串中的三个连续颜色组成。但为了进行搜索，我们需要由字符组成的常规三元组。在第三阶段，颜色三元组被扩展为常规三元组。由于每种颜色可以表示许多字符，扩展后的常规三元组的总数可能非常大。因为在索引中搜索数千个三元组会很慢，而且可能产生这样的误报以致我们必须遍历索引的大部分，因此通过消除颜色三元组以有损的方式进一步简化图。当一个颜色三元组被移除时，通过与该三元组标记的任何弧连接的状态将被合并。
 *
 * 三元组在搜索中并不都具有相等的价值：其中一些更频繁，而另一些则较少。理想情况下，我们希望知道三元组的分布，但我们并不知道。但由于填充，我们可以肯定，空字符比其他字符更频繁，因此我们可以根据空格的存在对三元组进行惩罚。分配给每个颜色三元组的惩罚是它将产生的简单三元组的数量，乘以与其空白内容相关的 penalties[] 乘数。（penalties[] 常量是通过对一些实际文本的分析计算得到的。）我们从惩罚最高的颜色三元组开始消除，直到总惩罚不超过 WISH_TRGM_PENALTY。然而，如果这将导致合并初始状态和最终状态，我们可能无法达到 WISH_TRGM_PENALTY。只要我们总的简单三元组不超过 MAX_TRGM_COUNT，这仍然是可以的，否则我们就失败。
 *
 * 4) 将图打包为紧凑表示
 * -----------------------------------------------
 * 第二和第三阶段可能已经消除或合并了之前创建的许多状态和三元组，因此在最后阶段，图被压缩并打包到一个更简单的结构中，仅包含评估所需的信息。
 *
 * 算法示例：
 *
 * 考虑示例正则表达式 "ab[cd]"。该正则表达式被转换为以下 NFA（为简便起见，我们显示颜色作为其单个成员）：
 *
 *					  4#
 *					c/
 *		 a	   b	/
 *	 1* --- 2 ---- 3
 *					\
 *					d\
 *					  5#
 *
 * 我们用 * 标记初始状态，用 # 标记最终状态。虽然未显示，但状态 1、4、5 对于所有可能的字符都有自引用弧，因为此模式可以匹配字符串的任何部分。
 *
 * 作为第二阶段的结果，我们将得到以下图：
 *
 *		  abc	 abd
 *	 2# <---- 1* ----> 3#
 *
 * 生成此图的过程是：
 * 1) 创建状态 1 并提供进入键 (UNKNOWN, UNKNOWN, 1)。
 * 2) 向状态 1 添加键 (UNKNOWN, "a", 2)。
 * 3) 向状态 1 添加键 ("a", "b", 3)。
 * 4) 创建新状态 2，并提供进入键 ("b", "c", 4)。从状态 1 向状态 2 添加一条标记三元组 "abc" 的弧。
 * 5) 标记状态 2 为最终状态，因为源 NFA 的状态 4 已标记为最终状态。
 * 6) 创建新状态 3，并提供进入键 ("b", "d", 5)。从状态 1 向状态 3 添加一条标记三元组 "abd" 的弧。
 * 7) 标记状态 3 为最终状态，因为源 NFA 的状态 5 已标记为最终状态。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  contrib/pg_trgm/trgm_regexp.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "regex/regexport.h"
#include "trgm.h"
#include "tsearch/ts_locale.h"
#include "utils/hsearch.h"
#include "utils/memutils.h"

/*
 * 取消注释（或使用 -DTRGM_REGEXP_DEBUG）以打印调试信息，
 * 以便探索和调试算法实现。
 * 这将在 /tmp 中生成三个图形文件，格式为 Graphviz .gv。
 * 一些进度信息也会打印到 postmaster stderr。
 */
/* #define TRGM_REGEXP_DEBUG */

/*
 * 这些参数用于限制工作的数量。
 * 否则，正则表达式处理可能会过慢并消耗内存。
 *
 *	MAX_EXPANDED_STATES - 我们允许在扩展图中有多少状态
 *	MAX_EXPANDED_ARCS - 我们允许在扩展图中有多少弧
 *	MAX_TRGM_COUNT - 我们允许提取多少个简单三元组
 *	WISH_TRGM_PENALTY - 颜色三元组罚款的最大期望总和
 *	COLOR_COUNT_LIMIT - 每种颜色的最大字符数
 */
#define MAX_EXPANDED_STATES 128
#define MAX_EXPANDED_ARCS	1024
#define MAX_TRGM_COUNT		256
#define WISH_TRGM_PENALTY	16
#define COLOR_COUNT_LIMIT	256

/*
 * 根据空白内容的三元组计数的罚款乘数。
 * 数字基于真实文本的分析。
 */
static const float4 penalties[8] = {
	1.0f,						/* "aaa" */
	3.5f,						/* "aa " */
	0.0f,						/* "a a"（不可能） */
	0.0f,						/* "a  "（不可能） */
	4.2f,						/* " aa" */
	2.1f,						/* " a " */
	25.0f,						/* "  a" */
	0.0f						/* "   "（不可能） */
};

/* 表示单个 pg_wchar 的结构，转换回多字节形式 */
typedef struct
{
	char		bytes[MAX_MULTIBYTE_CHAR_LEN];
} trgm_mb_char;

/*
 * NFA 颜色的属性：
 *
 *	expandable				- 我们知道此颜色的字符扩展
 *	containsNonWord			- 颜色包含非单词字符
 *							  （这些字符将不会被提取到三元组中）
 *	wordCharsCount			- 该颜色中单词字符的数量
 *	wordChars				- 该颜色的单词字符数组
 *							  （这些字符可以被提取到三元组中）
 *
 * 当 expandable 为 false 时，其他属性就不重要了；我们只是
 * 假设这个颜色代表未知字符。
 */
typedef struct
{
	bool		expandable;
	bool		containsNonWord;
	int			wordCharsCount;
	trgm_mb_char *wordChars;
} TrgmColorInfo;

/*
 * “前缀”是关于读取的最后两个字符的颜色的信息，
 * 在到达特定的 NFA 状态之前。这些颜色可以具有特殊值
 * COLOR_UNKNOWN 和 COLOR_BLANK。COLOR_UNKNOWN 表示我们没有
 * 信息，例如因为我们读取了一些不可扩展
 * 颜色的字符。COLOR_BLANK 表示我们读取了一个非单词字符。
 *
 * 如果前缀的至少一个颜色未知，我们称其为模糊前缀。它是
 * 完全模糊的，如果两个都是未知的；如果只有第一个
 * 是未知的，则是部分模糊的。（第一颜色已知，第二未知的情况是不 valid 的。）
 *
 * 完全或部分空白的前缀通常与常规颜色前缀的处理方式相同。
 * 这使我们能够在 NFA 要求单词字符与非单词字符相邻出现时生成适当的部分空白
 * 三元组。
 */
typedef int TrgmColor;

/* 我们假设正则表达式引擎返回的颜色不能是这些： */
#define COLOR_UNKNOWN	(-3)
#define COLOR_BLANK		(-4)

typedef struct
{
	TrgmColor	colors[2];
} TrgmPrefix;

/*
 * 颜色三元组数据类型。注意，三元组的一些元素可以是
 * COLOR_BLANK，但我们不允许 COLOR_UNKNOWN。
 */
typedef struct
{
	TrgmColor	colors[3];
} ColorTrgm;

/*
 * 识别我们扩展图的状态的键：颜色前缀，以及在基础正则表达式 NFA 中对应状态的编号。颜色前缀显示了我们如何到达正则表达式状态（在我们知道的范围内）。
 */
typedef struct
{
	TrgmPrefix	prefix;
	int			nstate;
} TrgmStateKey;

/*
 * 扩展图的一个状态。
 *
 *	stateKey - 此状态的 ID
 *	arcs	 - 此状态的出弧（TrgmArc 列表）
 *	enterKeys - 从此状态可达的进入键，无需读取任何可预测的三元组（TrgmStateKey 列表）
 *	flags	 - 标志位
 *	snumber  - 此状态的编号（初始分配为 -1、-2 等，仅用于调试目的；然后在打包阶段，存活的状态将重新编号为正数）
 *	parent	 - 父状态，如果此状态已与另一个状态合并
 *	tentFlags - 此状态将在计划合并时获得的标志
 *	tentParent - 计划的父状态，如果考虑合并
 */
#define TSTATE_INIT		0x01	/* 表示此状态是初始状态的标志 */
#define TSTATE_FIN		0x02	/* 表示此状态是最终状态的标志 */

typedef struct TrgmState
{
	TrgmStateKey stateKey;		/* 哈希表键：必须是第一个字段 */
	List	   *arcs;
	List	   *enterKeys;
	int			flags;
	int			snumber;
	struct TrgmState *parent;
	int			tentFlags;
	struct TrgmState *tentParent;
} TrgmState;

/*
 * 扩展图中的一条弧。
 */
typedef struct
{
	ColorTrgm	ctrgm;			/* 遍历弧所需的三元组 */
	TrgmState  *target;			/* 下一个状态 */
} TrgmArc;

/*
 * 关于特定颜色三元组的弧的信息（在第 3 阶段使用）
 *
 * 包含指向源和目标状态的指针。
 */
typedef struct
{
	TrgmState  *source;
	TrgmState  *target;
} TrgmArcInfo;

/*
 * 关于颜色三元组的信息（在第 3 阶段使用）
 *
 * ctrgm	- 三元组本身
 * cnumber	- 此三元组的编号（用于打包阶段）
 * count	- 从此颜色三元组创建的简单三元组的数量
 * expanded - 表示此颜色三元组已扩展为简单三元组
 * arcs		- 以此颜色三元组标记的所有弧的列表。
 */
typedef struct
{
	ColorTrgm	ctrgm;
	int			cnumber;
	int			count;
	float4		penalty;
	bool		expanded;
	List	   *arcs;
} ColorTrgmInfo;

/*
 * 表示在正则表达式处理过程中所需的所有数据的数据结构。
 *
 *	regex			- 编译后的正则表达式
 *	colorInfo		- 提取的有关正则表达式颜色的信息
 *	ncolors			- colorInfo[] 中的颜色数量
 *	states			- TrgmStates 的哈希表（扩展图的状态）
 *	initState		- 指向扩展图初始状态的指针
 *	queue			- 待处理 TrgmStates 的队列
 *	keysQueue		- 待处理 TrgmStateKeys 的队列
 *	arcsCount		- 扩展图的总弧数（用于资源限制）
 *	overflowed		- 我们已经超出了转换的资源限制
 *	colorTrgms		- 图中所有颜色三元组的数组
 *	colorTrgmsCount - 这些颜色三元组的计数
 *	totalTrgmCount	- 提取的简单三元组的总计数
 */
typedef struct
{
	/* 源正则表达式及其提取的颜色信息（第 1 阶段） */
	regex_t    *regex;
	TrgmColorInfo *colorInfo;
	int			ncolors;

	/* 扩展图（第 2 阶段） */
	HTAB	   *states;
	TrgmState  *initState;
	int			nstates;

	/* 第 2 阶段的工作区 */
	List	   *queue;
	List	   *keysQueue;
	int			arcsCount;
	bool		overflowed;

	/* 关于图中不同颜色三元组的信息（第 3 阶段） */
	ColorTrgmInfo *colorTrgms;
	int			colorTrgmsCount;
	int			totalTrgmCount;
} TrgmNFA;

/*
 * 扩展图的最终紧凑表示。
 */
typedef struct
{
	int			targetState;	/* 目标状态的索引（零基） */
	int			colorTrgm;		/* 转换的颜色三元组索引 */
} TrgmPackedArc;

typedef struct
{
	int			arcsCount;		/* 此状态的出弧数量 */
	TrgmPackedArc *arcs;		/* arcsCount 打包弧的数组 */
} TrgmPackedState;

/* "typedef struct TrgmPackedGraph TrgmPackedGraph" 出现在 trgm.h 中 */
struct TrgmPackedGraph
{
	/*
	 * colorTrigramsCount 和 colorTrigramGroups 包含有关三元组如何被分组为颜色三元组的信息。"colorTrigramsCount" 是颜色三元组的计数，而 "colorTrigramGroups" 包含每个颜色三元组的简单三元组数量。简单三元组的数组（与此结构单独存储）是有序的，以便每个颜色三元组的简单三元组是连续的，并且它们按颜色三元组编号排列。
	 */
	int			colorTrigramsCount;
	int		   *colorTrigramGroups; /* 大小为 colorTrigramsCount 的数组 */

	/*
	 * 简化 NFA 的状态。状态编号 0 始终是初始状态，状态编号 1 始终是最终状态。
	 */
	int			statesCount;
	TrgmPackedState *states;	/* 大小为 statesCount 的数组 */

	/* trigramsMatchGraph() 的临时工作空间 */
	bool	   *colorTrigramsActive;	/* 大小为 colorTrigramsCount 的数组 */
	bool	   *statesActive;	/* 大小为 statesCount 的数组 */
	int		   *statesQueue;	/* 大小为 statesCount 的数组 */
};

/*
 * 打包时表示弧的临时结构。
 */
typedef struct
{
	int			sourceState;
	int			targetState;
	int			colorTrgm;
} TrgmPackArcInfo;


/* 私有函数的原型 */
static TRGM *fc_createTrgmNFAInternal(regex_t *fc_regex, TrgmPackedGraph **fc_graph,
								   MemoryContext fc_rcontext);
static void fc_RE_compile(regex_t *fc_regex, text *fc_text_re,
					   int fc_cflags, Oid fc_collation);
static void fc_getColorInfo(regex_t *fc_regex, TrgmNFA *fc_trgmNFA);
static bool fc_convertPgWchar(pg_wchar fc_c, trgm_mb_char *fc_result);
static void fc_transformGraph(TrgmNFA *fc_trgmNFA);
static void fc_processState(TrgmNFA *fc_trgmNFA, TrgmState *fc_state);
static void fc_addKey(TrgmNFA *fc_trgmNFA, TrgmState *fc_state, TrgmStateKey *fc_key);
static void fc_addKeyToQueue(TrgmNFA *fc_trgmNFA, TrgmStateKey *fc_key);
static void fc_addArcs(TrgmNFA *fc_trgmNFA, TrgmState *fc_state);
static void fc_addArc(TrgmNFA *fc_trgmNFA, TrgmState *fc_state, TrgmStateKey *fc_key,
				   TrgmColor fc_co, TrgmStateKey *fc_destKey);
static bool fc_validArcLabel(TrgmStateKey *fc_key, TrgmColor fc_co);
static TrgmState *fc_getState(TrgmNFA *fc_trgmNFA, TrgmStateKey *fc_key);
static bool fc_prefixContains(TrgmPrefix *fc_prefix1, TrgmPrefix *fc_prefix2);
static bool fc_selectColorTrigrams(TrgmNFA *fc_trgmNFA);
static TRGM *fc_expandColorTrigrams(TrgmNFA *fc_trgmNFA, MemoryContext fc_rcontext);
static void fc_fillTrgm(trgm *fc_ptrgm, trgm_mb_char fc_s[3]);
static void fc_mergeStates(TrgmState *fc_state1, TrgmState *fc_state2);
static int	fc_colorTrgmInfoCmp(const void *fc_p1, const void *fc_p2);
static int	fc_colorTrgmInfoPenaltyCmp(const void *fc_p1, const void *fc_p2);
static TrgmPackedGraph *fc_packGraph(TrgmNFA *fc_trgmNFA, MemoryContext fc_rcontext);
static int	fc_packArcInfoCmp(const void *fc_a1, const void *fc_a2);

#ifdef TRGM_REGEXP_DEBUG
static void fc_printSourceNFA(regex_t *fc_regex, TrgmColorInfo *fc_colors, int fc_ncolors);
static void fc_printTrgmNFA(TrgmNFA *fc_trgmNFA);
static void fc_printTrgmColor(StringInfo fc_buf, TrgmColor fc_co);
static void fc_printTrgmPackedGraph(TrgmPackedGraph *fc_packedGraph, TRGM *fc_trigrams);
#endif


/*
 * 处理正则表达式的主要入口点。
 *
 * 返回一个正则表达式所需的三元组数组，如果正则表达式太复杂以至于无法分析，则返回 NULL。此外，将正则表达式的打包图形表示返回到 *graph。结果必须在 rcontext 中分配（当前上下文可能是也可能不是）。
 */
TRGM * createTrgmNFA(text *fc_text_re, Oid fc_collation,
			  TrgmPackedGraph **fc_graph, MemoryContext fc_rcontext)
{
	TRGM	   *fc_trg;
	regex_t		fc_regex;
	MemoryContext fc_tmpcontext;
	MemoryContext fc_oldcontext;

	/*
	 * 此处理会生成大量的杂物，我们希望在返回之前清理（因为此函数可能在查询生命周期内存上下文中被调用）。创建一个临时上下文，以便我们可以轻松地进行清理。
	 */
	fc_tmpcontext = AllocSetContextCreate(CurrentMemoryContext,
									   "createTrgmNFA temporary context",
									   ALLOCSET_DEFAULT_SIZES);
	fc_oldcontext = MemoryContextSwitchTo(fc_tmpcontext);

	/*
	 * 阶段 1：使用正则表达式库将正则表达式编译成 NFA。
	 */
#ifdef IGNORECASE
	fc_RE_compile(&fc_regex, fc_text_re,
			   REG_ADVANCED | REG_NOSUB | REG_ICASE, fc_collation);
#else
	RE_compile(&fc_regex, fc_text_re,
			   REG_ADVANCED | REG_NOSUB, fc_collation);
#endif

	/*
	 * 由于正则表达式库使用 malloc 分配其内部数据结构，我们需要使用 PG_TRY 块以确保即使发生错误也能完成 pg_regfree()。
	 */
	PG_TRY();
	{
		fc_trg = fc_createTrgmNFAInternal(&fc_regex, fc_graph, fc_rcontext);
	}
	PG_FINALLY();
	{
		pg_regfree(&fc_regex);
	}
	PG_END_TRY();

	/* 清理我们创建的所有杂物 */
	MemoryContextSwitchTo(fc_oldcontext);
	MemoryContextDelete(fc_tmpcontext);

	return fc_trg;
}

/*
 * createTrgmNFA 的主体，排除正则表达式编译/释放。
 */
static TRGM * fc_createTrgmNFAInternal(regex_t *fc_regex, TrgmPackedGraph **fc_graph,
					  MemoryContext fc_rcontext)
{
	TRGM	   *fc_trg;
	TrgmNFA		fc_trgmNFA;

	fc_trgmNFA.regex = fc_regex;

	/* 从正则表达式收集颜色信息 */
	fc_getColorInfo(fc_regex, &fc_trgmNFA);

#ifdef TRGM_REGEXP_DEBUG
	fc_printSourceNFA(fc_regex, fc_trgmNFA.colorInfo, fc_trgmNFA.ncolors);
#endif

	/*
	 * 阶段 2：从源 NFA 创建扩展图。
	 */
	fc_transformGraph(&fc_trgmNFA);

#ifdef TRGM_REGEXP_DEBUG
	fc_printTrgmNFA(&fc_trgmNFA);
#endif

	/*
	 * 如果无法创建非平凡图，则失败，即可能在不读取任何可预测三元组的情况下从初始状态到达最终状态。
	 */
	if (fc_trgmNFA.initState->flags & TSTATE_FIN)
		return NULL;

	/*
	 * 阶段 3：选择要扩展的颜色三元组。如果三元组过多则失败。
	 */
	if (!fc_selectColorTrigrams(&fc_trgmNFA))
		return NULL;

	/*
	 * 阶段 4：扩展颜色三元组并将图形打包为最终表示。
	 */
	fc_trg = fc_expandColorTrigrams(&fc_trgmNFA, fc_rcontext);

	*fc_graph = fc_packGraph(&fc_trgmNFA, fc_rcontext);

#ifdef TRGM_REGEXP_DEBUG
	fc_printTrgmPackedGraph(*fc_graph, fc_trg);
#endif

	return fc_trg;
}

/*
 * 在索引扫描期间评估图的主要入口点。
 *
 * check[] 数组按三元组编号（在 createTrgmNFA 返回的简单三元组数组中）进行索引，并对那些存在于被检查的索引条目中的三元组为真。
 */
bool trigramsMatchGraph(TrgmPackedGraph *fc_graph, bool *fc_check)
{
	int			fc_i,
				fc_j,
				fc_k,
				fc_queueIn,
				fc_queueOut;

	/*
	 * 重置临时工作区。
	 */
	memset(fc_graph->colorTrigramsActive, 0,
		   sizeof(bool) * fc_graph->colorTrigramsCount);
	memset(fc_graph->statesActive, 0, sizeof(bool) * fc_graph->statesCount);

	/*
	 * 检查匹配的颜色三元组。 任何与颜色三元组相关的简单三元组的匹配都算作颜色三元组的匹配。
	 */
	fc_j = 0;
	for (fc_i = 0; fc_i < fc_graph->colorTrigramsCount; fc_i++)
	{
		int			fc_cnt = fc_graph->colorTrigramGroups[fc_i];

		for (fc_k = fc_j; fc_k < fc_j + fc_cnt; fc_k++)
		{
			if (fc_check[fc_k])
			{
				/*
				 * 在组中找到了一个匹配的三元组。 可以跳过其余的三元组，转到下一个组。
				 */
				fc_graph->colorTrigramsActive[fc_i] = true;
				break;
			}
		}
		fc_j = fc_j + fc_cnt;
	}

	/*
	 * 初始化 statesQueue，以仅容纳初始状态。 注意：statesQueue 有足够容纳 statesCount 条目，肯定足够，因为不会将同一状态多次放入队列中。 statesActive 数组标记哪些状态已被排入队列。
	 */
	fc_graph->statesActive[0] = true;
	fc_graph->statesQueue[0] = 0;
	fc_queueIn = 0;
	fc_queueOut = 1;

	/* 处理排队的状态，只要还有状态。 */
	while (fc_queueIn < fc_queueOut)
	{
		int			fc_stateno = fc_graph->statesQueue[fc_queueIn++];
		TrgmPackedState *fc_state = &fc_graph->states[fc_stateno];
		int			fc_cnt = fc_state->arcsCount;

		/* 循环遍历状态的出弧 */
		for (fc_i = 0; fc_i < fc_cnt; fc_i++)
		{
			TrgmPackedArc *fc_arc = &fc_state->arcs[fc_i];

			/*
			 * 如果存在对应的颜色三元组，则激活相应的状态。 如果这是最终状态，我们就完成了，否则如果尚未入队则将状态排入队列。
			 */
			if (fc_graph->colorTrigramsActive[fc_arc->colorTrgm])
			{
				int			fc_nextstate = fc_arc->targetState;

				if (fc_nextstate == 1)
					return true;	/* 成功：最终状态可达 */

				if (!fc_graph->statesActive[fc_nextstate])
				{
					fc_graph->statesActive[fc_nextstate] = true;
					fc_graph->statesQueue[fc_queueOut++] = fc_nextstate;
				}
			}
		}
	}

	/* 队列为空，因此匹配失败。 */
	return false;
}

/*
 * 将正则表达式字符串编译到 *regex 的结构中。
 * 注意：如果成功完成，必须对 regex 应用 pg_regfree。
 */
static void fc_RE_compile(regex_t *fc_regex, text *fc_text_re, int fc_cflags, Oid fc_collation)
{
	int			fc_text_re_len = VARSIZE_ANY_EXHDR(fc_text_re);
	char	   *fc_text_re_val = VARDATA_ANY(fc_text_re);
	pg_wchar   *fc_pattern;
	int			fc_pattern_len;
	int			fc_regcomp_result;
	char		fc_errMsg[100];

	/* 将模式字符串转换为宽字符 */
	fc_pattern = (pg_wchar *) palloc((fc_text_re_len + 1) * sizeof(pg_wchar));
	fc_pattern_len = pg_mb2wchar_with_len(fc_text_re_val,
									   fc_pattern,
									   fc_text_re_len);

	/* 编译正则表达式 */
	fc_regcomp_result = pg_regcomp(fc_regex,
								fc_pattern,
								fc_pattern_len,
								fc_cflags,
								fc_collation);

	pfree(fc_pattern);

	if (fc_regcomp_result != REG_OKAY)
	{
		/* re 未成功编译（如果是这样，则无需 pg_regfree） */
		pg_regerror(fc_regcomp_result, fc_regex, fc_errMsg, sizeof(fc_errMsg));
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
				 errmsg("invalid regular expression: %s", fc_errMsg)));
	}
}


/*---------------------
 * 颜色映射的预处理子例程（阶段 1）。
 *---------------------
 */

/*
 * 使用正则表达式导出函数填充每种颜色的 TrgmColorInfo 结构。
 */
static void fc_getColorInfo(regex_t *fc_regex, TrgmNFA *fc_trgmNFA)
{
	int			fc_colorsCount = pg_reg_getnumcolors(fc_regex);
	int			fc_i;

	fc_trgmNFA->ncolors = fc_colorsCount;
	fc_trgmNFA->colorInfo = (TrgmColorInfo *)
		palloc0(fc_colorsCount * sizeof(TrgmColorInfo));

	/*
	 * 循环遍历颜色，填充每种颜色的 TrgmColorInfo。 注意，我们包括白色 (0)，即使我们知道它将被报告为不可扩展。
	 */
	for (fc_i = 0; fc_i < fc_colorsCount; fc_i++)
	{
		TrgmColorInfo *fc_colorInfo = &fc_trgmNFA->colorInfo[fc_i];
		int			fc_charsCount = pg_reg_getnumcharacters(fc_regex, fc_i);
		pg_wchar   *fc_chars;
		int			fc_j;

		if (fc_charsCount < 0 || fc_charsCount > COLOR_COUNT_LIMIT)
		{
			/* 不可扩展，或过大而无法处理 */
			fc_colorInfo->expandable = false;
			continue;
		}

		fc_colorInfo->expandable = true;
		fc_colorInfo->containsNonWord = false;
		fc_colorInfo->wordChars = (trgm_mb_char *)
			palloc(sizeof(trgm_mb_char) * fc_charsCount);
		fc_colorInfo->wordCharsCount = 0;

		/* 提取此颜色中的所有字符 */
		fc_chars = (pg_wchar *) palloc(sizeof(pg_wchar) * fc_charsCount);
		pg_reg_getcharacters(fc_regex, fc_i, fc_chars, fc_charsCount);

		/*
		 * 将字符转换回多字节形式，仅保留单词字符。 如果有任何非单词字符，则设置 "containsNonWord"。 （注意：现在保留 pg_wchar 格式的字符可能会更好，但 ISWORDCHR 想要看到多字节。）
		 */
		for (fc_j = 0; fc_j < fc_charsCount; fc_j++)
		{
			trgm_mb_char fc_c;

			if (!fc_convertPgWchar(fc_chars[fc_j], &fc_c))
				continue;		/* 完全可以忽略它 */
			if (ISWORDCHR(fc_c.bytes))
				fc_colorInfo->wordChars[fc_colorInfo->wordCharsCount++] = fc_c;
			else
				fc_colorInfo->containsNonWord = true;
		}

		pfree(fc_chars);
	}
}

/*
 * 将 pg_wchar 转换为多字节格式。
 * 如果该字符应该被完全忽略，则返回 false。
 */
static bool fc_convertPgWchar(pg_wchar fc_c, trgm_mb_char *fc_result)
{
	/* "s" 为多字节字符和尾随 NUL 留有足够的空间 */
	char		fc_s[MAX_MULTIBYTE_CHAR_LEN + 1];

	/*
	 * 我们可以忽略 NUL 字符，因为它永远不会出现在 PG 文本字符串中。 这避免了在重构三元组时需要多种特殊情况。
	 */
	if (fc_c == 0)
		return false;

	/* 进行转换，确保结果以 NUL 终止 */
	memset(fc_s, 0, sizeof(fc_s));
	pg_wchar2mb_with_len(&fc_c, fc_s, 1);

	/*
	 * 在IGNORECASE模式下，我们可以忽略大写字符。我们假设
	 * 正则表达式引擎在每种颜色内生成了大写和小写的等价物，
	 * 因为我们使用了REG_ICASE选项；所以没有必要处理大写版本。
	 *
	 * XXX 这段代码依赖于lowerstr()与正则表达式引擎内部大小写折叠机制
	 * 是相同的假设。如果存在任何不兼容，可能更明智的做法是暴露pg_wc_tolower，
	 * 并测试c == pg_wc_tolower(c)。另一方面，索引中的三元组是使用
	 * lowerstr()创建的，因此如果存在不兼容，我们可能无路可退。
	 */
#ifdef IGNORECASE
	{
		char	   *fc_lowerCased = lowerstr(fc_s);

		if (strcmp(fc_lowerCased, fc_s) != 0)
		{
			pfree(fc_lowerCased);
			return false;
		}
		pfree(fc_lowerCased);
	}
#endif

	/* 用准确的MAX_MULTIBYTE_CHAR_LEN字节填充结果 */
	memcpy(fc_result->bytes, fc_s, MAX_MULTIBYTE_CHAR_LEN);
	return true;
}


/*---------------------
 * 将原始NFA图扩展为三元图的子例程（阶段2）。
 *---------------------
 */

/*
 * 给定正则表达式和提取的颜色信息，转换图形。
 *
 * 我们创建并处理一个扩展图状态的队列，直到所有状态
 * 都被处理。
 *
 * 由于资源限制，这个算法可以被停止。在这种情况下，我们
 * 强制每个未处理的分支立即完成匹配（这可能会给我们带来假阳性，
 * 但没有假阴性），方法是将所有未处理的状态标记为最终状态。
 */
static void fc_transformGraph(TrgmNFA *fc_trgmNFA)
{
	HASHCTL		fc_hashCtl;
	TrgmStateKey fc_initkey;
	TrgmState  *fc_initstate;
	ListCell   *fc_lc;

	/* 初始化此阶段在trgmNFA结构中的工作区 */
	fc_trgmNFA->queue = NIL;
	fc_trgmNFA->keysQueue = NIL;
	fc_trgmNFA->arcsCount = 0;
	fc_trgmNFA->overflowed = false;

	/* 为状态创建哈希表 */
	fc_hashCtl.keysize = sizeof(TrgmStateKey);
	fc_hashCtl.entrysize = sizeof(TrgmState);
	fc_hashCtl.hcxt = CurrentMemoryContext;
	fc_trgmNFA->states = hash_create("Trigram NFA",
								  1024,
								  &fc_hashCtl,
								  HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
	fc_trgmNFA->nstates = 0;

	/* 创建初始状态：模糊前缀，NFA的初始状态 */
	MemSet(&fc_initkey, 0, sizeof(fc_initkey));
	fc_initkey.prefix.colors[0] = COLOR_UNKNOWN;
	fc_initkey.prefix.colors[1] = COLOR_UNKNOWN;
	fc_initkey.nstate = pg_reg_getinitialstate(fc_trgmNFA->regex);

	fc_initstate = fc_getState(fc_trgmNFA, &fc_initkey);
	fc_initstate->flags |= TSTATE_INIT;
	fc_trgmNFA->initState = fc_initstate;

	/*
	 * 通过处理状态队列（广度优先搜索）递归构建扩展图。
	 * getState已经将initstate放入队列中。
	 * 注意，getState在循环中也会将新状态追加到队列；
	 * 只要我们不使用“lc”指针进行重复获取，这样就可以工作。
	 */
	foreach(fc_lc, fc_trgmNFA->queue)
	{
		TrgmState  *fc_state = (TrgmState *) lfirst(fc_lc);

		/*
		 * 如果我们溢出，则只将状态标记为最终状态。否则，进行
		 * 实际处理。
		 */
		if (fc_trgmNFA->overflowed)
			fc_state->flags |= TSTATE_FIN;
		else
			fc_processState(fc_trgmNFA, fc_state);

		/* 我们溢出了吗？ */
		if (fc_trgmNFA->arcsCount > MAX_EXPANDED_ARCS ||
			hash_get_num_entries(fc_trgmNFA->states) > MAX_EXPANDED_STATES)
			fc_trgmNFA->overflowed = true;
	}
}

/*
 * 处理一个状态：添加进入键，然后添加出弧。
 */
static void fc_processState(TrgmNFA *fc_trgmNFA, TrgmState *fc_state)
{
	ListCell   *fc_lc;

	/* keysQueue应该已经是NIL，但确保一下 */
	fc_trgmNFA->keysQueue = NIL;

	/*
	 * 添加状态自己的键，然后处理添加到keysQueue的所有键，直到
	 * 队列处理完。但如果状态被标记为最终状态，我们可以退出。
	 */
	fc_addKey(fc_trgmNFA, fc_state, &fc_state->stateKey);
	foreach(fc_lc, fc_trgmNFA->keysQueue)
	{
		TrgmStateKey *fc_key = (TrgmStateKey *) lfirst(fc_lc);

		if (fc_state->flags & TSTATE_FIN)
			break;
		fc_addKey(fc_trgmNFA, fc_state, fc_key);
	}

	/* 释放keysQueue以进行下一个循环的清理 */
	list_free(fc_trgmNFA->keysQueue);
	fc_trgmNFA->keysQueue = NIL;

	/*
	 * 只有在状态不是最终状态时才添加出弧（如果我们已经匹配，
	 * 我们对出弧没有兴趣）
	 */
	if (!(fc_state->flags & TSTATE_FIN))
		fc_addArcs(fc_trgmNFA, fc_state);
}

/*
 * 将给定的输入键添加到状态的 enterKeys 列表中，并确定
 * 是否应因此添加其他输入键。
 * 如果是，将这些键添加到 keysQueue，以便 processState 进行处理。
 *
 * 如果输入键是 NFA 的终态，则将状态标记为 TSTATE_FIN。
 * 这种情况意味着我们可以从这个扩展状态到达终态，而不需要读取任何可预测的三元组，因此我们必须将此状态视为一个接受状态。
 *
 * 给定的键可能是已经在 enterKeys 中的重复项，或者与某些 enterKeys 冗余。
 * 所以在进行任何操作之前我们要检查这一点。
 *
 * 注意，我们在这里不生成任何实际的弧。 addArcs 会在后面处理这些
 * ，当我们识别出这个状态的所有输入键时。
 */
static void fc_addKey(TrgmNFA *fc_trgmNFA, TrgmState *fc_state, TrgmStateKey *fc_key)
{
	regex_arc_t *fc_arcs;
	TrgmStateKey fc_destKey;
	ListCell   *fc_cell;
	int			fc_i,
				fc_arcsCount;

	/*
	 * 确保 destKey 中的任何填充字节为零，因为它可能被 getState 用作
	 * 哈希表键。
	 */
	MemSet(&fc_destKey, 0, sizeof(fc_destKey));

	/*
	 * 比较键与状态的每个现有输入键以检查冗余。如果我们发现
	 * 冗余，可以放弃旧的键或新的键。
	 */
	foreach(fc_cell, fc_state->enterKeys)
	{
		TrgmStateKey *fc_existingKey = (TrgmStateKey *) lfirst(fc_cell);

		if (fc_existingKey->nstate == fc_key->nstate)
		{
			if (fc_prefixContains(&fc_existingKey->prefix, &fc_key->prefix))
			{
				/* 这个旧键已经覆盖了新键。无需操作 */
				return;
			}
			if (fc_prefixContains(&fc_key->prefix, &fc_existingKey->prefix))
			{
				/*
				 * 新键覆盖了这个旧键。移除旧键，添加这个键到列表后
				 * 它不再需要。
				 */
				fc_state->enterKeys = foreach_delete_current(fc_state->enterKeys,
														  fc_cell);
			}
		}
	}

	/* 没有冗余，因此将这个键添加到状态的列表中 */
	fc_state->enterKeys = lappend(fc_state->enterKeys, fc_key);

	/* 如果状态现在被知晓为终态，则标记它，我们完成了 */
	if (fc_key->nstate == pg_reg_getfinalstate(fc_trgmNFA->regex))
	{
		fc_state->flags |= TSTATE_FIN;
		return;
	}

	/*
	 * 循环遍历原始 NFA 中对应状态的所有出弧。
	 */
	fc_arcsCount = pg_reg_getnumoutarcs(fc_trgmNFA->regex, fc_key->nstate);
	fc_arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * fc_arcsCount);
	pg_reg_getoutarcs(fc_trgmNFA->regex, fc_key->nstate, fc_arcs, fc_arcsCount);

	for (fc_i = 0; fc_i < fc_arcsCount; fc_i++)
	{
		regex_arc_t *fc_arc = &fc_arcs[fc_i];

		if (pg_reg_colorisbegin(fc_trgmNFA->regex, fc_arc->co))
		{
			/*
			 * 行/字符串的开始 (^)。三元组提取将行开始视为
			 * 单词的开始：添加双空格前缀。
			 * 因此，创建一个输入键，表示我们可以在全空前缀的情况下
			 * 到达弧的目的地。
			 */
			fc_destKey.prefix.colors[0] = COLOR_BLANK;
			fc_destKey.prefix.colors[1] = COLOR_BLANK;
			fc_destKey.nstate = fc_arc->to;

			/* 将输入键添加到这个状态 */
			fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
		}
		else if (pg_reg_colorisend(fc_trgmNFA->regex, fc_arc->co))
		{
			/*
			 * 行/字符串的结束 ($)。我们必须将此弧视为
			 * 不读取任何内容的转换。添加此输入键到状态的原因在于
			 * 如果弧引导至 NFA 的终态，则必须将此扩展状态标记为终态。
			 */
			fc_destKey.prefix.colors[0] = COLOR_UNKNOWN;
			fc_destKey.prefix.colors[1] = COLOR_UNKNOWN;
			fc_destKey.nstate = fc_arc->to;

			/* 将输入键添加到这个状态 */
			fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
		}
		else if (fc_arc->co >= 0)
		{
			/* 常规颜色（包括 WHITE） */
			TrgmColorInfo *fc_colorInfo = &fc_trgmNFA->colorInfo[fc_arc->co];

			if (fc_colorInfo->expandable)
			{
				if (fc_colorInfo->containsNonWord &&
					!fc_validArcLabel(fc_key, COLOR_BLANK))
				{
					/*
					 * 我们可以在读取非单词字符后到达弧的目的地，
					 * 但前缀不是 addArc 将接受的 COLOR_BLANK，
					 * 因此无法为此转换生成三元组弧。我们必须创建一个
					 * 输入键以表明弧的目的地是可达的。将其设置为全空前缀，
					 * 因为这对应于三元组提取代码在单词开始边界的处理。
					 */
					fc_destKey.prefix.colors[0] = COLOR_BLANK;
					fc_destKey.prefix.colors[1] = COLOR_BLANK;
					fc_destKey.nstate = fc_arc->to;
					fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
				}

				if (fc_colorInfo->wordCharsCount > 0 &&
					!fc_validArcLabel(fc_key, fc_arc->co))
				{
					/*
					 * 我们可以在读取一个单词字符后到达弧的目标，
					 * 但前缀不是 addArc 可以接受的，因此无法为此
					 * 转换生成三元弧。我们必须创建一个进入键以表明弧的目标是可达的。
					 * 进入键的前缀应该反映我们对于这个弧的信息。
					 */
					fc_destKey.prefix.colors[0] = fc_key->prefix.colors[1];
					fc_destKey.prefix.colors[1] = fc_arc->co;
					fc_destKey.nstate = fc_arc->to;
					fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
				}
			}
			else
			{
				/*
				 * 非可扩展颜色。添加具有模糊前缀的进入键，
				 * 显示我们可以从这个状态到达目标，但
				 * 前面的颜色将是不确定的。（我们不将
				 * 第一个前缀颜色设置为 key->prefix.colors[1]，因为已知的前缀后跟未知是无效的。）
				 */
				fc_destKey.prefix.colors[0] = COLOR_UNKNOWN;
				fc_destKey.prefix.colors[1] = COLOR_UNKNOWN;
				fc_destKey.nstate = fc_arc->to;
				fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
			}
		}
		else
		{
			/* 彩虹：视为非可扩展颜色 */
			fc_destKey.prefix.colors[0] = COLOR_UNKNOWN;
			fc_destKey.prefix.colors[1] = COLOR_UNKNOWN;
			fc_destKey.nstate = fc_arc->to;
			fc_addKeyToQueue(fc_trgmNFA, &fc_destKey);
		}
	}

	pfree(fc_arcs);
}

/*
 * 将给定键的副本添加到 keysQueue，以便后续处理。
 */
static void fc_addKeyToQueue(TrgmNFA *fc_trgmNFA, TrgmStateKey *fc_key)
{
	TrgmStateKey *fc_keyCopy = (TrgmStateKey *) palloc(sizeof(TrgmStateKey));

	memcpy(fc_keyCopy, fc_key, sizeof(TrgmStateKey));
	fc_trgmNFA->keysQueue = lappend(fc_trgmNFA->keysQueue, fc_keyCopy);
}

/*
 * 从给定状态添加出弧，所有进入键现在都是已知的。
 */
static void fc_addArcs(TrgmNFA *fc_trgmNFA, TrgmState *fc_state)
{
	TrgmStateKey fc_destKey;
	ListCell   *fc_cell;
	regex_arc_t *fc_arcs;
	int			fc_arcsCount,
				fc_i;

	/*
	 * 确保 destKey 中的任何填充字节为零，因为它可能被 getState 用作
	 * 哈希表键。
	 */
	MemSet(&fc_destKey, 0, sizeof(fc_destKey));

	/*
	 * 迭代与这个扩展图状态相关的进入键。这包括
	 * 状态自己的 stateKey，以及在 addKey 期间
	 * 添加到它的任何进入键（这些进入键表示通过三元组无法与此状态区分的扩展图状态）。
	 * 对于每个这样的进入键，检查键的基础 NFA 状态的所有出弧，
	 * 并尝试生成一个指向出弧指向的位置的三元弧。
	 * （addArc 将处理弧是否有效的问题。）
	 */
	foreach(fc_cell, fc_state->enterKeys)
	{
		TrgmStateKey *fc_key = (TrgmStateKey *) lfirst(fc_cell);

		fc_arcsCount = pg_reg_getnumoutarcs(fc_trgmNFA->regex, fc_key->nstate);
		fc_arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * fc_arcsCount);
		pg_reg_getoutarcs(fc_trgmNFA->regex, fc_key->nstate, fc_arcs, fc_arcsCount);

		for (fc_i = 0; fc_i < fc_arcsCount; fc_i++)
		{
			regex_arc_t *fc_arc = &fc_arcs[fc_i];
			TrgmColorInfo *fc_colorInfo;

			/*
			 * 忽略不可扩展的颜色；addKey 已经处理过这个情况。
			 *
			 * 这里不需要对白色或开始/结束伪颜色进行特殊检查。
			 * 我们不需要对它们进行任何处理，因为它们
			 * 会被标记为不可扩展，因为正则表达式引擎会
			 * 以这种方式报告它们。我们确实需要注意彩虹，
			 * 它有一个负色号。
			 */
			if (fc_arc->co < 0)
				continue;
			Assert(fc_arc->co < fc_trgmNFA->ncolors);

			fc_colorInfo = &fc_trgmNFA->colorInfo[fc_arc->co];
			if (!fc_colorInfo->expandable)
				continue;

			if (fc_colorInfo->containsNonWord)
			{
				/*
				 * 颜色包含非单词字符。
				 *
				 * 生成一条弧，视此转换发生在
				 * 空白上。这可以制造出单词结尾的三元组。
				 */
				fc_destKey.prefix.colors[0] = fc_key->prefix.colors[1];
				fc_destKey.prefix.colors[1] = COLOR_BLANK;
				fc_destKey.nstate = fc_arc->to;

				fc_addArc(fc_trgmNFA, fc_state, fc_key, COLOR_BLANK, &fc_destKey);
			}

			if (fc_colorInfo->wordCharsCount > 0)
			{
				/*
				 * 颜色包含单词字符。
				 *
				 * 生成一条弧。颜色被推入目标
				 * 状态的前缀中。
				 */
				fc_destKey.prefix.colors[0] = fc_key->prefix.colors[1];
				fc_destKey.prefix.colors[1] = fc_arc->co;
				fc_destKey.nstate = fc_arc->to;

				fc_addArc(fc_trgmNFA, fc_state, fc_key, fc_arc->co, &fc_destKey);
			}
		}

		pfree(fc_arcs);
	}
}

/*
 * 如果它有效且不冗余，则生成扩展图的出弧。
 *
 * state: 我们想在其上添加出弧的扩展图状态
 * key: 提供前缀颜色（key->nstate 不使用）
 * co: 转换颜色
 * destKey: 扩展图目标状态的标识符
 */
static void fc_addArc(TrgmNFA *fc_trgmNFA, TrgmState *fc_state, TrgmStateKey *fc_key,
	   TrgmColor fc_co, TrgmStateKey *fc_destKey)
{
	TrgmArc    *fc_arc;
	ListCell   *fc_cell;

	/* 如果这不是有效的弧标签三元组，则不执行任何操作 */
	if (!fc_validArcLabel(fc_key, fc_co))
		return;

	/*
	 * 检查我们是否将到达已被
	 * 此状态中已列出的键覆盖的键。如果是，则弧是无用的：
	 * NFA 可以通过不需要任何可预测三元组的路径绕过它，
	 * 因此弧的三元组是否存在实际上并不重要。
	 */
	foreach(fc_cell, fc_state->enterKeys)
	{
		TrgmStateKey *fc_existingKey = (TrgmStateKey *) lfirst(fc_cell);

		if (fc_existingKey->nstate == fc_destKey->nstate &&
			fc_prefixContains(&fc_existingKey->prefix, &fc_destKey->prefix))
			return;
	}

	/* 检查成功，添加新弧 */
	fc_arc = (TrgmArc *) palloc(sizeof(TrgmArc));
	fc_arc->target = fc_getState(fc_trgmNFA, fc_destKey);
	fc_arc->ctrgm.colors[0] = fc_key->prefix.colors[0];
	fc_arc->ctrgm.colors[1] = fc_key->prefix.colors[1];
	fc_arc->ctrgm.colors[2] = fc_co;

	fc_state->arcs = lappend(fc_state->arcs, fc_arc);
	fc_trgmNFA->arcsCount++;
}

/*
 * 我们能从给定的前缀和弧颜色制作有效的三元组弧标签吗？
 *
 * 这是分开的，以便在 addKey 和 addArc 中的测试能够保持同步。
 */
static bool fc_validArcLabel(TrgmStateKey *fc_key, TrgmColor fc_co)
{
	/*
	 * 我们必须知道完整的三元组才能添加出弧。所以如果前缀模糊
	 * 我们不能这样做。
	 */
	if (fc_key->prefix.colors[0] == COLOR_UNKNOWN)
		return false;

	/* 如果 key->prefix.colors[0] 不是未知的，那么其第二种颜色也不是 */
	Assert(fc_key->prefix.colors[1] != COLOR_UNKNOWN);
	/* 我们不应该在任何时候被调用未知的弧颜色 */
	Assert(fc_co != COLOR_UNKNOWN);

	/*
	 * 我们不关心表示三个非单词字符的弧，因为这对三元组提取
	 * 是无用的。
	 */
	if (fc_key->prefix.colors[0] == COLOR_BLANK &&
		fc_key->prefix.colors[1] == COLOR_BLANK &&
		fc_co == COLOR_BLANK)
		return false;

	/*
	 * 我们也会拒绝非空-空-任何。非空-空-非空的情况
	 * 不对应于三元组提取代码会生成的任何三元组。非空-空-空的情况
	 * 在 RPADDING = 1 的情况下也是不可能的。 （注意，在许多情况下，
	 * 即使它是有效的，我们也会失败生成这样的三元组，比如处理
	 * "foo bar" 不会考虑到三元组 "o  "。所以如果你想支持
	 * RPADDING = 2，还有更多的工作要做，而不仅仅是调整这个测试。）
	 */
	if (fc_key->prefix.colors[0] != COLOR_BLANK &&
		fc_key->prefix.colors[1] == COLOR_BLANK)
		return false;

	/*
	 * 其他涉及空格的组合是有效的，特别是我们假设
	 * 空-空-非空是有效的，这假定 LPADDING 为 2。
	 *
	 * 注意：再以 "foo bar" 为例，我们将不会考虑
	 * 三元组 "  b"，尽管这个三元组会被三元组
	 * 提取代码找到。由于我们会找到 " ba"，因此似乎没有必要尝试
	 * 黑客算法以生成额外的三元组。
	 */

	/* 弧标签是有效的 */
	return true;
}

/*
 * 获取给定状态键的扩展图的状态，
 * 并将状态排队以进行处理，如果它尚不存在。
 */
static TrgmState *
fc_getState(TrgmNFA *fc_trgmNFA, TrgmStateKey *fc_key)
{
	TrgmState  *fc_state;
	bool		fc_found;

	fc_state = (TrgmState *) hash_search(fc_trgmNFA->states, fc_key, HASH_ENTER,
									  &fc_found);
	if (!fc_found)
	{
		/* 新状态：初始化并排队 */
		fc_state->arcs = NIL;
		fc_state->enterKeys = NIL;
		fc_state->flags = 0;
		/* 状态最初被赋予负数 */
		fc_state->snumber = -(++fc_trgmNFA->nstates);
		fc_state->parent = NULL;
		fc_state->tentFlags = 0;
		fc_state->tentParent = NULL;

		fc_trgmNFA->queue = lappend(fc_trgmNFA->queue, fc_state);
	}
	return fc_state;
}

/*
 * 检查 prefix1 是否“包含” prefix2。
 *
 * “包含”意味着任何满足 prefix2 的精确前缀（没有歧义）
 * 也满足 prefix1。
 */
static bool fc_prefixContains(TrgmPrefix *fc_prefix1, TrgmPrefix *fc_prefix2)
{
	if (fc_prefix1->colors[1] == COLOR_UNKNOWN)
	{
		/* 完全模糊的前缀包含一切 */
		return true;
	}
	else if (fc_prefix1->colors[0] == COLOR_UNKNOWN)
	{
		/*
		 * 仅具有第一个未知颜色的前缀包含每个具有
		 * 相同第二种颜色的前缀。
		 */
		if (fc_prefix1->colors[1] == fc_prefix2->colors[1])
			return true;
		else
			return false;
	}
	else
	{
		/* 精确前缀仅包含完全相同的前缀 */
		if (fc_prefix1->colors[0] == fc_prefix2->colors[0] &&
			fc_prefix1->colors[1] == fc_prefix2->colors[1])
			return true;
		else
			return false;
	}
}


/*---------------------
 * 将颜色三元组扩展为常规三元组的子例程（阶段 3）。
 *---------------------
 */

/*
 * 获取图中所有颜色三元组的向量，并选择其中哪些
 * 扩展为简单三元组。
 *
 * 如果可以则返回真，若耗尽资源限制则返回假。
 */
static bool fc_selectColorTrigrams(TrgmNFA *fc_trgmNFA)
{
	HASH_SEQ_STATUS fc_scan_status;
	int			fc_arcsCount = fc_trgmNFA->arcsCount,
				fc_i;
	TrgmState  *fc_state;
	ColorTrgmInfo *fc_colorTrgms;
	int64		fc_totalTrgmCount;
	float4		fc_totalTrgmPenalty;
	int			fc_cnumber;

	/* 从所有弧收集颜色三元组 */
	fc_colorTrgms = (ColorTrgmInfo *) palloc0(sizeof(ColorTrgmInfo) * fc_arcsCount);
	fc_trgmNFA->colorTrgms = fc_colorTrgms;

	fc_i = 0;
	hash_seq_init(&fc_scan_status, fc_trgmNFA->states);
	while ((fc_state = (TrgmState *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		ListCell   *fc_cell;

		foreach(fc_cell, fc_state->arcs)
		{
			TrgmArc    *fc_arc = (TrgmArc *) lfirst(fc_cell);
			TrgmArcInfo *fc_arcInfo = (TrgmArcInfo *) palloc(sizeof(TrgmArcInfo));
			ColorTrgmInfo *fc_trgmInfo = &fc_colorTrgms[fc_i];

			fc_arcInfo->source = fc_state;
			fc_arcInfo->target = fc_arc->target;
			fc_trgmInfo->ctrgm = fc_arc->ctrgm;
			fc_trgmInfo->cnumber = -1;
			/* 计数和惩罚将在下文中设置 */
			fc_trgmInfo->expanded = true;
			fc_trgmInfo->arcs = list_make1(fc_arcInfo);
			fc_i++;
		}
	}
	Assert(fc_i == fc_arcsCount);

	/* 移除重复项，合并它们的弧列表 */
	if (fc_arcsCount >= 2)
	{
		ColorTrgmInfo *fc_p1,
				   *fc_p2;

		/* 排序三元组以便于重复检测 */
		qsort(fc_colorTrgms, fc_arcsCount, sizeof(ColorTrgmInfo), fc_colorTrgmInfoCmp);

		/* p1 是探测点，p2 是最后已知的非重复项。 */
		fc_p2 = fc_colorTrgms;
		for (fc_p1 = fc_colorTrgms + 1; fc_p1 < fc_colorTrgms + fc_arcsCount; fc_p1++)
		{
			if (fc_colorTrgmInfoCmp(fc_p1, fc_p2) > 0)
			{
				fc_p2++;
				*fc_p2 = *fc_p1;
			}
			else
			{
				fc_p2->arcs = list_concat(fc_p2->arcs, fc_p1->arcs);
			}
		}
		fc_trgmNFA->colorTrgmsCount = (fc_p2 - fc_colorTrgms) + 1;
	}
	else
	{
		fc_trgmNFA->colorTrgmsCount = fc_arcsCount;
	}

	/*
	 * 计算每个颜色三元组生成的简单三元组数量，并
	 * 计算一个惩罚值，即简单三元组的数量乘以一个依赖于其空格内容的乘数。
	 *
	 * 注意：每个颜色三元组的计数在不超过 COLOR_COUNT_LIMIT 的情况下
	 * 不能溢出一个 int，因此 COLOR_COUNT_LIMIT 不能超过 INT_MAX 的立方根，即大约
	 * 1290。然而，总代码总数 totalTrgmCount 可能会溢出 int，所以我们在这个例程中使用 int64。同时，
	 * 为避免任何溢出担忧，惩罚值是以 float4 算术进行计算的。
	 */
	fc_totalTrgmCount = 0;
	fc_totalTrgmPenalty = 0.0f;
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		ColorTrgmInfo *fc_trgmInfo = &fc_colorTrgms[fc_i];
		int			fc_j,
					fc_count = 1,
					fc_typeIndex = 0;

		for (fc_j = 0; fc_j < 3; fc_j++)
		{
			TrgmColor	fc_c = fc_trgmInfo->ctrgm.colors[fc_j];

			fc_typeIndex *= 2;
			if (fc_c == COLOR_BLANK)
				fc_typeIndex++;
			else
				fc_count *= fc_trgmNFA->colorInfo[fc_c].wordCharsCount;
		}
		fc_trgmInfo->count = fc_count;
		fc_totalTrgmCount += fc_count;
		fc_trgmInfo->penalty = penalties[fc_typeIndex] * (float4) fc_count;
		fc_totalTrgmPenalty += fc_trgmInfo->penalty;
	}

	/* 按照惩罚值的降序排列颜色三元组 */
	qsort(fc_colorTrgms, fc_trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
		  fc_colorTrgmInfoPenaltyCmp);

	/*
	 * 从图中删除颜色三元组，只要颜色三元组的总惩罚超过 WISH_TRGM_PENALTY。
	 * （如果我们未能降到 WISH_TRGM_PENALTY，没关系，只要总数不超过
	 * MAX_TRGM_COUNT。）我们更倾向于删除惩罚较高的颜色三元组，
	 * 因为这些三元组最有可能减少总惩罚。当删除颜色三元组时，我们必须合并
	 * 被该三元组标记的弧连接的状态。必须注意不要合并初始和结束状态，
	 * 因为如果发生这种情况，我们的图将变得无用；因此我们并不总是能够删除
	 * 我们希望删除的三元组。
	 */
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		ColorTrgmInfo *fc_trgmInfo = &fc_colorTrgms[fc_i];
		bool		fc_canRemove = true;
		ListCell   *fc_cell;

		/* 如果我们已经达到了目标，完成 */
		if (fc_totalTrgmPenalty <= WISH_TRGM_PENALTY)
			break;

#ifdef TRGM_REGEXP_DEBUG
		fprintf(stderr, "considering ctrgm %d %d %d, penalty %f, %d arcs\n",
				fc_trgmInfo->ctrgm.colors[0],
				fc_trgmInfo->ctrgm.colors[1],
				fc_trgmInfo->ctrgm.colors[2],
				fc_trgmInfo->penalty,
				list_length(fc_trgmInfo->arcs));
#endif

		/*
		 * 这个颜色三元组的任何弧是否连接初始和结束状态？
		 * 如果是，我们就无法删除它。
		 */
		foreach(fc_cell, fc_trgmInfo->arcs)
		{
			TrgmArcInfo *fc_arcInfo = (TrgmArcInfo *) lfirst(fc_cell);
			TrgmState  *fc_source = fc_arcInfo->source,
					   *fc_target = fc_arcInfo->target;
			int			fc_source_flags,
						fc_target_flags;

#ifdef TRGM_REGEXP_DEBUG
			fprintf(stderr, "examining arc to s%d (%x) from s%d (%x)\n",
					-fc_target->snumber, fc_target->flags,
					-fc_source->snumber, fc_source->flags);
#endif

			/* 检查父状态，如果已经发生了合并 */
			while (fc_source->parent)
				fc_source = fc_source->parent;
			while (fc_target->parent)
				fc_target = fc_target->parent;

#ifdef TRGM_REGEXP_DEBUG
			fprintf(stderr, " ... after completed merges: to s%d (%x) from s%d (%x)\n",
					-fc_target->snumber, fc_target->flags,
					-fc_source->snumber, fc_source->flags);
#endif

			/* 我们还必须考虑我们当前计划的合并 */
			fc_source_flags = fc_source->flags | fc_source->tentFlags;
			while (fc_source->tentParent)
			{
				fc_source = fc_source->tentParent;
				fc_source_flags |= fc_source->flags | fc_source->tentFlags;
			}
			fc_target_flags = fc_target->flags | fc_target->tentFlags;
			while (fc_target->tentParent)
			{
				fc_target = fc_target->tentParent;
				fc_target_flags |= fc_target->flags | fc_target->tentFlags;
			}

#ifdef TRGM_REGEXP_DEBUG
			fprintf(stderr, " ... after tentative merges: to s%d (%x) from s%d (%x)\n",
					-fc_target->snumber, fc_target_flags,
					-fc_source->snumber, fc_source_flags);
#endif

			/* 完全合并的状态是否同时设置了 INIT 和 FIN？ */
			if (((fc_source_flags | fc_target_flags) & (TSTATE_INIT | TSTATE_FIN)) ==
				(TSTATE_INIT | TSTATE_FIN))
			{
				fc_canRemove = false;
				break;
			}

			/* 到目前为止没问题，所以记住计划的合并 */
			if (fc_source != fc_target)
			{
#ifdef TRGM_REGEXP_DEBUG
				fprintf(stderr, " ... tentatively merging s%d into s%d\n",
						-fc_target->snumber, -fc_source->snumber);
#endif
				fc_target->tentParent = fc_source;
				fc_source->tentFlags |= fc_target_flags;
			}
		}

		/*
		 * 我们必须在继续之前重置所有的 tentFlags/tentParent 字段。
		 * tentFlags 只能在当前弧的源状态、父状态或临时父状态中设置；
		 * 同样，tentParent 只能在当前弧的目标状态、父状态或临时父状态中设置。
		 * 这些集合之间可能会有一些重叠，但如果我们在目标状态和源状态中
		 * 清除 tentFlags，那么即使我们在作为目标状态访问一个状态之前
		 * 先访问它作为源状态，我们也应该没问题。
		 */
		foreach(fc_cell, fc_trgmInfo->arcs)
		{
			TrgmArcInfo *fc_arcInfo = (TrgmArcInfo *) lfirst(fc_cell);
			TrgmState  *fc_source = fc_arcInfo->source,
					   *fc_target = fc_arcInfo->target;
			TrgmState  *fc_ttarget;

			/* 无需触及之前合并的状态 */
			while (fc_source->parent)
				fc_source = fc_source->parent;
			while (fc_target->parent)
				fc_target = fc_target->parent;

			while (fc_source)
			{
				fc_source->tentFlags = 0;
				fc_source = fc_source->tentParent;
			}

			while ((fc_ttarget = fc_target->tentParent) != NULL)
			{
				fc_target->tentParent = NULL;
				fc_target->tentFlags = 0;	/* 以防它也是一个源 */
				fc_target = fc_ttarget;
			}
		}

		/* 现在，如果我们无法删除这个三元组，就继续前进 */
		if (!fc_canRemove)
		{
#ifdef TRGM_REGEXP_DEBUG
			fprintf(stderr, " ... not ok to merge\n");
#endif
			continue;
		}

		/* 好的，合并每个由三元组标记的弧链接的状态 */
		foreach(fc_cell, fc_trgmInfo->arcs)
		{
			TrgmArcInfo *fc_arcInfo = (TrgmArcInfo *) lfirst(fc_cell);
			TrgmState  *fc_source = fc_arcInfo->source,
					   *fc_target = fc_arcInfo->target;

			while (fc_source->parent)
				fc_source = fc_source->parent;
			while (fc_target->parent)
				fc_target = fc_target->parent;
			if (fc_source != fc_target)
			{
#ifdef TRGM_REGEXP_DEBUG
				fprintf(stderr, "merging s%d into s%d\n",
						-fc_target->snumber, -fc_source->snumber);
#endif
				fc_mergeStates(fc_source, fc_target);
				/* 断言我们没有合并初始和结束状态 */
				Assert((fc_source->flags & (TSTATE_INIT | TSTATE_FIN)) !=
					   (TSTATE_INIT | TSTATE_FIN));
			}
		}

		/* 标记三元组未展开，并更新总数 */
		fc_trgmInfo->expanded = false;
		fc_totalTrgmCount -= fc_trgmInfo->count;
		fc_totalTrgmPenalty -= fc_trgmInfo->penalty;
	}

	/* 我们成功适应了 MAX_TRGM_COUNT 吗？ */
	if (fc_totalTrgmCount > MAX_TRGM_COUNT)
		return false;

	fc_trgmNFA->totalTrgmCount = (int) fc_totalTrgmCount;

	/*
	 * 按颜色对颜色三元组进行排序（这将对 packGraph 中的二分搜索非常有用）
	 * 并列举已展开的颜色三元组。
	 */
	fc_cnumber = 0;
	qsort(fc_colorTrgms, fc_trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
		  fc_colorTrgmInfoCmp);
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		if (fc_colorTrgms[fc_i].expanded)
		{
			fc_colorTrgms[fc_i].cnumber = fc_cnumber;
			fc_cnumber++;
		}
	}

	return true;
}

/*
 * 扩展所选颜色三元组为常规三元组。
 *
 * 返回要传递给索引机制的 TRGM 数组。
 * 数组必须在 rcontext 中分配。
 */
static TRGM * fc_expandColorTrigrams(TrgmNFA *fc_trgmNFA, MemoryContext fc_rcontext)
{
	TRGM	   *fc_trg;
	trgm	   *fc_p;
	int			fc_i;
	TrgmColorInfo fc_blankColor;
	trgm_mb_char fc_blankChar;

	/* 设置包含单个零字符的“空白”颜色结构 */
	memset(fc_blankChar.bytes, 0, sizeof(fc_blankChar.bytes));
	fc_blankColor.wordCharsCount = 1;
	fc_blankColor.wordChars = &fc_blankChar;

	/* 构造 trgm 数组 */
	fc_trg = (TRGM *)
		MemoryContextAllocZero(fc_rcontext,
							   TRGMHDRSIZE +
							   fc_trgmNFA->totalTrgmCount * sizeof(trgm));
	fc_trg->flag = ARRKEY;
	SET_VARSIZE(fc_trg, CALCGTSIZE(ARRKEY, fc_trgmNFA->totalTrgmCount));
	fc_p = GETARR(fc_trg);
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		ColorTrgmInfo *fc_colorTrgm = &fc_trgmNFA->colorTrgms[fc_i];
		TrgmColorInfo *fc_c[3];
		trgm_mb_char fc_s[3];
		int			fc_j,
					fc_i1,
					fc_i2,
					fc_i3;

		/* 忽略任何未扩展的三元组 ... */
		if (!fc_colorTrgm->expanded)
			continue;

		/* 获取颜色，用虚拟结构替代 COLOR_BLANK */
		for (fc_j = 0; fc_j < 3; fc_j++)
		{
			if (fc_colorTrgm->ctrgm.colors[fc_j] != COLOR_BLANK)
				fc_c[fc_j] = &fc_trgmNFA->colorInfo[fc_colorTrgm->ctrgm.colors[fc_j]];
			else
				fc_c[fc_j] = &fc_blankColor;
		}

		/* 遍历所有可能的颜色字符组合 */
		for (fc_i1 = 0; fc_i1 < fc_c[0]->wordCharsCount; fc_i1++)
		{
			fc_s[0] = fc_c[0]->wordChars[fc_i1];
			for (fc_i2 = 0; fc_i2 < fc_c[1]->wordCharsCount; fc_i2++)
			{
				fc_s[1] = fc_c[1]->wordChars[fc_i2];
				for (fc_i3 = 0; fc_i3 < fc_c[2]->wordCharsCount; fc_i3++)
				{
					fc_s[2] = fc_c[2]->wordChars[fc_i3];
					fc_fillTrgm(fc_p, fc_s);
					fc_p++;
				}
			}
		}
	}

	return fc_trg;
}

/*
 * 将三元组转换为 trgm 数据类型。
 */
static void fc_fillTrgm(trgm *fc_ptrgm, trgm_mb_char fc_s[3])
{
	char		fc_str[3 * MAX_MULTIBYTE_CHAR_LEN],
			   *fc_p;
	int			fc_i,
				fc_j;

	/* 将多字节字符串写入“str”（我们不需要空终止） */
	fc_p = fc_str;

	for (fc_i = 0; fc_i < 3; fc_i++)
	{
		if (fc_s[fc_i].bytes[0] != 0)
		{
			for (fc_j = 0; fc_j < MAX_MULTIBYTE_CHAR_LEN && fc_s[fc_i].bytes[fc_j]; fc_j++)
				*fc_p++ = fc_s[fc_i].bytes[fc_j];
		}
		else
		{
			/* 用 COLOR_BLANK 代替发出一个空格 */
			*fc_p++ = ' ';
		}
	}

	/* 将“str”转换为标准三元组（可能进行哈希处理） */
	compact_trigram(fc_ptrgm, fc_str, fc_p - fc_str);
}

/*
 * 合并图的两个状态。
 */
static void fc_mergeStates(TrgmState *fc_state1, TrgmState *fc_state2)
{
	Assert(fc_state1 != fc_state2);
	Assert(!fc_state1->parent);
	Assert(!fc_state2->parent);

	/* state1 吸收 state2 的标志 */
	fc_state1->flags |= fc_state2->flags;

	/* state2 及其所有子级间接成为 state1 的子级 */
	fc_state2->parent = fc_state1;
}

/*
 * 按颜色对颜色三元组进行排序的比较函数。
 */
static int fc_colorTrgmInfoCmp(const void *fc_p1, const void *fc_p2)
{
	const ColorTrgmInfo *fc_c1 = (const ColorTrgmInfo *) fc_p1;
	const ColorTrgmInfo *fc_c2 = (const ColorTrgmInfo *) fc_p2;

	return memcmp(&fc_c1->ctrgm, &fc_c2->ctrgm, sizeof(ColorTrgm));
}

/*
 * 按其惩罚字段的降序对颜色三元组进行排序的比较函数。
 */
static int fc_colorTrgmInfoPenaltyCmp(const void *fc_p1, const void *fc_p2)
{
	float4		fc_penalty1 = ((const ColorTrgmInfo *) fc_p1)->penalty;
	float4		fc_penalty2 = ((const ColorTrgmInfo *) fc_p2)->penalty;

	if (fc_penalty1 < fc_penalty2)
		return 1;
	else if (fc_penalty1 == fc_penalty2)
		return 0;
	else
		return -1;
}


/*---------------------
 * 将图打包为最终表示的子程序（阶段 4）。
 *---------------------
 */

/*
 * 将扩展图打包为最终表示。
 *
 * 结果数据必须在 rcontext 中分配。
 */
static TrgmPackedGraph *
fc_packGraph(TrgmNFA *fc_trgmNFA, MemoryContext fc_rcontext)
{
	int			fc_snumber = 2,
				fc_arcIndex,
				fc_arcsCount;
	HASH_SEQ_STATUS fc_scan_status;
	TrgmState  *fc_state;
	TrgmPackArcInfo *fc_arcs;
	TrgmPackedArc *fc_packedArcs;
	TrgmPackedGraph *fc_result;
	int			fc_i,
				fc_j;

	/* 枚举存活状态，给 init 和 fin 保留号码 */
	hash_seq_init(&fc_scan_status, fc_trgmNFA->states);
	while ((fc_state = (TrgmState *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		while (fc_state->parent)
			fc_state = fc_state->parent;

		if (fc_state->snumber < 0)
		{
			if (fc_state->flags & TSTATE_INIT)
				fc_state->snumber = 0;
			else if (fc_state->flags & TSTATE_FIN)
				fc_state->snumber = 1;
			else
			{
				fc_state->snumber = fc_snumber;
				fc_snumber++;
			}
		}
	}

	/* 收集所有弧的数组 */
	fc_arcs = (TrgmPackArcInfo *)
		palloc(sizeof(TrgmPackArcInfo) * fc_trgmNFA->arcsCount);
	fc_arcIndex = 0;
	hash_seq_init(&fc_scan_status, fc_trgmNFA->states);
	while ((fc_state = (TrgmState *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		TrgmState  *fc_source = fc_state;
		ListCell   *fc_cell;

		while (fc_source->parent)
			fc_source = fc_source->parent;

		foreach(fc_cell, fc_state->arcs)
		{
			TrgmArc    *fc_arc = (TrgmArc *) lfirst(fc_cell);
			TrgmState  *fc_target = fc_arc->target;

			while (fc_target->parent)
				fc_target = fc_target->parent;

			if (fc_source->snumber != fc_target->snumber)
			{
				ColorTrgmInfo *fc_ctrgm;

				fc_ctrgm = (ColorTrgmInfo *) bsearch(&fc_arc->ctrgm,
												  fc_trgmNFA->colorTrgms,
												  fc_trgmNFA->colorTrgmsCount,
												  sizeof(ColorTrgmInfo),
												  fc_colorTrgmInfoCmp);
				Assert(fc_ctrgm != NULL);
				Assert(fc_ctrgm->expanded);

				fc_arcs[fc_arcIndex].sourceState = fc_source->snumber;
				fc_arcs[fc_arcIndex].targetState = fc_target->snumber;
				fc_arcs[fc_arcIndex].colorTrgm = fc_ctrgm->cnumber;
				fc_arcIndex++;
			}
		}
	}

	/* 排序弧以方便重复检测 */
	qsort(fc_arcs, fc_arcIndex, sizeof(TrgmPackArcInfo), fc_packArcInfoCmp);

	/* 由于状态被合并，我们可能会有重复项。移除它们。 */
	if (fc_arcIndex > 1)
	{
		/* p1 是探测点，p2 是最后已知的非重复项。 */
		TrgmPackArcInfo *fc_p1,
				   *fc_p2;

		fc_p2 = fc_arcs;
		for (fc_p1 = fc_arcs + 1; fc_p1 < fc_arcs + fc_arcIndex; fc_p1++)
		{
			if (fc_packArcInfoCmp(fc_p1, fc_p2) > 0)
			{
				fc_p2++;
				*fc_p2 = *fc_p1;
			}
		}
		fc_arcsCount = (fc_p2 - fc_arcs) + 1;
	}
	else
		fc_arcsCount = fc_arcIndex;

	/* 创建打包表示 */
	fc_result = (TrgmPackedGraph *)
		MemoryContextAlloc(fc_rcontext, sizeof(TrgmPackedGraph));

	/* 打包颜色三元组信息 */
	fc_result->colorTrigramsCount = 0;
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		if (fc_trgmNFA->colorTrgms[fc_i].expanded)
			fc_result->colorTrigramsCount++;
	}
	fc_result->colorTrigramGroups = (int *)
		MemoryContextAlloc(fc_rcontext, sizeof(int) * fc_result->colorTrigramsCount);
	fc_j = 0;
	for (fc_i = 0; fc_i < fc_trgmNFA->colorTrgmsCount; fc_i++)
	{
		if (fc_trgmNFA->colorTrgms[fc_i].expanded)
		{
			fc_result->colorTrigramGroups[fc_j] = fc_trgmNFA->colorTrgms[fc_i].count;
			fc_j++;
		}
	}

	/* 打包状态和弧信息 */
	fc_result->statesCount = fc_snumber;
	fc_result->states = (TrgmPackedState *)
		MemoryContextAlloc(fc_rcontext, fc_snumber * sizeof(TrgmPackedState));
	fc_packedArcs = (TrgmPackedArc *)
		MemoryContextAlloc(fc_rcontext, fc_arcsCount * sizeof(TrgmPackedArc));
	fc_j = 0;
	for (fc_i = 0; fc_i < fc_snumber; fc_i++)
	{
		int			fc_cnt = 0;

		fc_result->states[fc_i].arcs = &fc_packedArcs[fc_j];
		while (fc_j < fc_arcsCount && fc_arcs[fc_j].sourceState == fc_i)
		{
			fc_packedArcs[fc_j].targetState = fc_arcs[fc_j].targetState;
			fc_packedArcs[fc_j].colorTrgm = fc_arcs[fc_j].colorTrgm;
			fc_cnt++;
			fc_j++;
		}
		fc_result->states[fc_i].arcsCount = fc_cnt;
	}

	/* 为 trigramsMatchGraph() 分配工作内存 */
	fc_result->colorTrigramsActive = (bool *)
		MemoryContextAlloc(fc_rcontext, sizeof(bool) * fc_result->colorTrigramsCount);
	fc_result->statesActive = (bool *)
		MemoryContextAlloc(fc_rcontext, sizeof(bool) * fc_result->statesCount);
	fc_result->statesQueue = (int *)
		MemoryContextAlloc(fc_rcontext, sizeof(int) * fc_result->statesCount);

	return fc_result;
}

/*
 * 用于排序 TrgmPackArcInfos 的比较函数。
 *
 * 按以下顺序比较弧：sourceState, colorTrgm, targetState。
 */
static int fc_packArcInfoCmp(const void *fc_a1, const void *fc_a2)
{
	const TrgmPackArcInfo *fc_p1 = (const TrgmPackArcInfo *) fc_a1;
	const TrgmPackArcInfo *fc_p2 = (const TrgmPackArcInfo *) fc_a2;

	if (fc_p1->sourceState < fc_p2->sourceState)
		return -1;
	if (fc_p1->sourceState > fc_p2->sourceState)
		return 1;
	if (fc_p1->colorTrgm < fc_p2->colorTrgm)
		return -1;
	if (fc_p1->colorTrgm > fc_p2->colorTrgm)
		return 1;
	if (fc_p1->targetState < fc_p2->targetState)
		return -1;
	if (fc_p1->targetState > fc_p2->targetState)
		return 1;
	return 0;
}


/*---------------------
 * 调试函数
 *
 * 这些函数旨在生成 GraphViz 文件。
 *---------------------
 */

#ifdef TRGM_REGEXP_DEBUG

/*
 * 打印初始 NFA，以正则表达式库的表示形式
 */
static void fc_printSourceNFA(regex_t *fc_regex, TrgmColorInfo *fc_colors, int fc_ncolors)
{
	StringInfoData fc_buf;
	int			fc_nstates = pg_reg_getnumstates(fc_regex);
	int			fc_state;
	int			fc_i;

	initStringInfo(&fc_buf);

	appendStringInfoString(&fc_buf, "\ndigraph sourceNFA {\n");

	for (fc_state = 0; fc_state < fc_nstates; fc_state++)
	{
		regex_arc_t *fc_arcs;
		int			fc_i,
					fc_arcsCount;

		appendStringInfo(&fc_buf, "s%d", fc_state);
		if (pg_reg_getfinalstate(fc_regex) == fc_state)
			appendStringInfoString(&fc_buf, " [shape = doublecircle]");
		appendStringInfoString(&fc_buf, ";\n");

		fc_arcsCount = pg_reg_getnumoutarcs(fc_regex, fc_state);
		fc_arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * fc_arcsCount);
		pg_reg_getoutarcs(fc_regex, fc_state, fc_arcs, fc_arcsCount);

		for (fc_i = 0; fc_i < fc_arcsCount; fc_i++)
		{
			appendStringInfo(&fc_buf, "  s%d -> s%d [label = \"%d\"];\n",
							 fc_state, fc_arcs[fc_i].to, fc_arcs[fc_i].co);
		}

		pfree(fc_arcs);
	}

	appendStringInfoString(&fc_buf, " node [shape = point ]; initial;\n");
	appendStringInfo(&fc_buf, " initial -> s%d;\n",
					 pg_reg_getinitialstate(fc_regex));

	/* 打印颜色 */
	appendStringInfoString(&fc_buf, " { rank = sink;\n");
	appendStringInfoString(&fc_buf, "  Colors [shape = none, margin=0, label=<\n");

	for (fc_i = 0; fc_i < fc_ncolors; fc_i++)
	{
		TrgmColorInfo *fc_color = &fc_colors[fc_i];
		int			fc_j;

		appendStringInfo(&fc_buf, "<br/>Color %d: ", fc_i);
		if (fc_color->expandable)
		{
			for (fc_j = 0; fc_j < fc_color->wordCharsCount; fc_j++)
			{
				char		fc_s[MAX_MULTIBYTE_CHAR_LEN + 1];

				memcpy(fc_s, fc_color->wordChars[fc_j].bytes, MAX_MULTIBYTE_CHAR_LEN);
				fc_s[MAX_MULTIBYTE_CHAR_LEN] = '\0';
				appendStringInfoString(&fc_buf, fc_s);
			}
		}
		else
			appendStringInfoString(&fc_buf, "not expandable");
		appendStringInfoChar(&fc_buf, '\n');
	}

	appendStringInfoString(&fc_buf, "  >];\n");
	appendStringInfoString(&fc_buf, " }\n");
	appendStringInfoString(&fc_buf, "}\n");

	{
		/* dot -Tpng -o /tmp/source.png < /tmp/source.gv */
		FILE	   *fc_fp = fopen("/tmp/source.gv", "w");

		fprintf(fc_fp, "%s", fc_buf.data);
		fclose(fc_fp);
	}

	pfree(fc_buf.data);
}

/*
 * 打印扩展图。
 */
static void fc_printTrgmNFA(TrgmNFA *fc_trgmNFA)
{
	StringInfoData fc_buf;
	HASH_SEQ_STATUS fc_scan_status;
	TrgmState  *fc_state;
	TrgmState  *fc_initstate = NULL;

	initStringInfo(&fc_buf);

	appendStringInfoString(&fc_buf, "\ndigraph transformedNFA {\n");

	hash_seq_init(&fc_scan_status, fc_trgmNFA->states);
	while ((fc_state = (TrgmState *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		ListCell   *fc_cell;

		appendStringInfo(&fc_buf, "s%d", -fc_state->snumber);
		if (fc_state->flags & TSTATE_FIN)
			appendStringInfoString(&fc_buf, " [shape = doublecircle]");
		if (fc_state->flags & TSTATE_INIT)
			fc_initstate = fc_state;
		appendStringInfo(&fc_buf, " [label = \"%d\"]", fc_state->stateKey.nstate);
		appendStringInfoString(&fc_buf, ";\n");

		foreach(fc_cell, fc_state->arcs)
		{
			TrgmArc    *fc_arc = (TrgmArc *) lfirst(fc_cell);

			appendStringInfo(&fc_buf, "  s%d -> s%d [label = \"",
							 -fc_state->snumber, -fc_arc->target->snumber);
			fc_printTrgmColor(&fc_buf, fc_arc->ctrgm.colors[0]);
			appendStringInfoChar(&fc_buf, ' ');
			fc_printTrgmColor(&fc_buf, fc_arc->ctrgm.colors[1]);
			appendStringInfoChar(&fc_buf, ' ');
			fc_printTrgmColor(&fc_buf, fc_arc->ctrgm.colors[2]);
			appendStringInfoString(&fc_buf, "\"];\n");
		}
	}

	if (fc_initstate)
	{
		appendStringInfoString(&fc_buf, " node [shape = point ]; initial;\n");
		appendStringInfo(&fc_buf, " initial -> s%d;\n", -fc_initstate->snumber);
	}

	appendStringInfoString(&fc_buf, "}\n");

	{
		/* dot -Tpng -o /tmp/transformed.png < /tmp/transformed.gv */
		FILE	   *fc_fp = fopen("/tmp/transformed.gv", "w");

		fprintf(fc_fp, "%s", fc_buf.data);
		fclose(fc_fp);
	}

	pfree(fc_buf.data);
}

/*
 * 可读地打印 TrgmColor。
 */
static void fc_printTrgmColor(StringInfo fc_buf, TrgmColor fc_co)
{
	if (fc_co == COLOR_UNKNOWN)
		appendStringInfoChar(fc_buf, 'u');
	else if (fc_co == COLOR_BLANK)
		appendStringInfoChar(fc_buf, 'b');
	else
		appendStringInfo(fc_buf, "%d", (int) fc_co);
}

/*
 * 打印基于三元组的扩展图的最终打包表示。
 */
static void fc_printTrgmPackedGraph(TrgmPackedGraph *fc_packedGraph, TRGM *fc_trigrams)
{
	StringInfoData fc_buf;
	trgm	   *fc_p;
	int			fc_i;

	initStringInfo(&fc_buf);

	appendStringInfoString(&fc_buf, "\ndigraph packedGraph {\n");

	for (fc_i = 0; fc_i < fc_packedGraph->statesCount; fc_i++)
	{
		TrgmPackedState *fc_state = &fc_packedGraph->states[fc_i];
		int			fc_j;

		appendStringInfo(&fc_buf, " s%d", fc_i);
		if (fc_i == 1)
			appendStringInfoString(&fc_buf, " [shape = doublecircle]");

		appendStringInfo(&fc_buf, " [label = <s%d>];\n", fc_i);

		for (fc_j = 0; fc_j < fc_state->arcsCount; fc_j++)
		{
			TrgmPackedArc *fc_arc = &fc_state->arcs[fc_j];

			appendStringInfo(&fc_buf, "  s%d -> s%d [label = \"trigram %d\"];\n",
							 fc_i, fc_arc->targetState, fc_arc->colorTrgm);
		}
	}

	appendStringInfoString(&fc_buf, " node [shape = point ]; initial;\n");
	appendStringInfo(&fc_buf, " initial -> s%d;\n", 0);

	/* 打印三元组 */
	appendStringInfoString(&fc_buf, " { rank = sink;\n");
	appendStringInfoString(&fc_buf, "  Trigrams [shape = none, margin=0, label=<\n");

	fc_p = GETARR(fc_trigrams);
	for (fc_i = 0; fc_i < fc_packedGraph->colorTrigramsCount; fc_i++)
	{
		int			fc_count = fc_packedGraph->colorTrigramGroups[fc_i];
		int			fc_j;

		appendStringInfo(&fc_buf, "<br/>Trigram %d: ", fc_i);

		for (fc_j = 0; fc_j < fc_count; fc_j++)
		{
			if (fc_j > 0)
				appendStringInfoString(&fc_buf, ", ");

			/*
			 * XXX 该表示仅对全 ASCII 三元组有效。
			 */
			appendStringInfo(&fc_buf, "\"%c%c%c\"", (*fc_p)[0], (*fc_p)[1], (*fc_p)[2]);
			fc_p++;
		}
	}

	appendStringInfoString(&fc_buf, "  >];\n");
	appendStringInfoString(&fc_buf, " }\n");
	appendStringInfoString(&fc_buf, "}\n");

	{
		/* dot -Tpng -o /tmp/packed.png < /tmp/packed.gv */
		FILE	   *fc_fp = fopen("/tmp/packed.gv", "w");

		fprintf(fc_fp, "%s", fc_buf.data);
		fclose(fc_fp);
	}

	pfree(fc_buf.data);
}

#endif							/* TRGM_REGEXP_DEBUG */
